package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/2/4 11:05
 * @Version 1.0
 **/
public class UniquePaths {


    /**
     * 解法一：动态规划 -- 状态转移方程 -- map[i][j] = map[i][j-1] + map[i-1][j] --  注意初始条件map[1][1] = 1
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] map = new int[m+1][n+1];
        map[1][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                map[i][j] += map[i][j-1] + map[i-1][j];
            }
        }
        return map[m][n];
    }

    /**
     * 解法二：利用排列组合  start->finish 共有m+n-2步，从中选m-1向右走 n-1向左走  即可 即C(m+n-2,m-1)
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths2(int m, int n) {
        int result = 1;
        for (int i = 1; i <= n-1; i++) {
            // 这里是先计算乘法可能会爆，可以使用C(x,y)的动态规划解法，计算C(m+n-2,m-1)的值
            result = result*(m+n-1-i)/i;
        }
        return result;
    }
}
